package com.example.leetcode.prcatice;

/**
 * 数组中占比超过一半的元素称之为主要元素。给你一个 整数 数组，找出其中的主要元素。若没有，返回 -1 。请设计时间复杂度为 O(N) 、空间复杂度为 O(1) 的解决方案。
 *
 * <p>
 *
 * <p>示例 1：
 *
 * <p>输入：[1,2,5,9,5,9,5,5,5] 输出：5
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/find-majority-element-lcci
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Test1710 {
    /**
     * 候选人思路，假定第一个人是候选人，遇到相同的票就加，不同就减
     * @param nums
     * @return
     */
    public int majorityElement(int[] nums) {
        int start = nums[0];
        int count = 1;
        for (int i=1;i<nums.length;i++){
            if(count ==0){
                count++;
                start = nums[i];
            }else if(start == nums[i]){
                count++;
            }else {
                count--;
            }
        }
        count = 0;
        for ( int i:nums ) {
            if (start == i){
                count++;
            }
        }
        return count*2 > nums.length? start:-1;
    }
}


class Demo1710{
  public static void main(String[] args) {
    Test1710 t = new Test1710();
    int[] nums = {1,1,1,2,2,3,3}; //像这种例子，即使一开始候选人是1号，减到最后start = 3，但3没有一般所以为-1，如果有候选人，那么他就有一半以上
      // 减到start就是他，count>=0
    System.out.println(t.majorityElement(nums));
  }
}